package J4_12;

import java.util.*;

public class test {
    //如果序列 X_1, X_2, ..., X_n 满足下列条件，就说它是 斐波那契式 的：
    //
    //n >= 3
    //对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}
    //给定一个严格递增的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在，返回  0 。
    //
    //（回想一下，子序列是从原序列 arr 中派生出来的，它从 arr 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列）

    public static int lenLongestFibSubseq(int[] nums) {
        int n = nums.length;
        HashMap<Integer,Integer> map = new HashMap<>();
        int[][] dp = new int[n][n];
        for (int i = 0;i < n; i++) Arrays.fill(dp[i],2);
        map.put(nums[0],0);
        int max = 2;
        for (int i = 1 ; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (map.containsKey(nums[j] - nums[i])) {
                    dp[i][j] = dp[map.get(nums[j]-nums[i])][i] + 1;

                }
                max = Math.max(max,dp[i][j]);
            }
            map.put(nums[i],i);
        }
        return max < 3 ? 0 : max;
    }


    //给你一个整数数组 nums ，返回 nums 中所有 等差子序列 的数目。
    //
    //如果一个序列中 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该序列为等差序列。
    //
    //例如，[1, 3, 5, 7, 9]、[7, 7, 7, 7] 和 [3, -1, -5, -9] 都是等差序列。
    //再例如，[1, 1, 2, 5, 7] 不是等差序列。
    //数组中的子序列是从数组中删除一些元素（也可能不删除）得到的一个序列。
    //
    //例如，[2,5,10] 是 [1,2,1,2,4,1,5,10] 的一个子序列。
    //题目数据保证答案是一个 32-bit 整数。
    public int numberOfArithmeticSlices(int[] nums) {
        Map<Long, List<Integer>> hash = new HashMap<>();
        int n = nums.length;
        for(int i = 0; i < n; i++)
        {
            long tmp = (long)nums[i];
            if(!hash.containsKey(tmp))
                hash.put(tmp, new ArrayList<Integer>());
            hash.get(tmp).add(i);
        }
        int[][] dp = new int[n][n];
        int sum = 0;
        for(int j = 2; j < n; j++) // 固定倒数第⼀个数
            for(int i = 1; i < j; i++) // 枚举倒数第⼆个数
            {
                long a = 2L * nums[i] - nums[j];
                if(hash.containsKey(a))
                {
                    for(int k : hash.get(a))
                        if(k < i) dp[i][j] += dp[k][i] + 1;
                        else break; // ⼩优化
                }
                sum += dp[i][j];
                }
        return sum;
    }


    public static void main(String[] args) {
        int[] arr = {2,4,5,6,7,8,11,13,14,15,21,22,34};
        int str = lenLongestFibSubseq(arr);
        System.out.println();

    }
}
